{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<p style=\"text-align: center;font-size: 33px;font-weight:bold;\"> <span style=\"color:DarkGoldenrod\">&lt;&lt; C程序的基本要素 &gt;&gt;</span></p>\n",
    "<p style=\"text-align: center;font-size: 25px;font-weight:bold;\"> <span style=\"color:Goldenrod\">&lt;&lt; Programming Basics using C Language  &gt;&gt;</span></p>\n",
    "<p style=\"text-align: right; font-size:15px; font-weight:normal\">----千里之行，基于硅步</p>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 函数\n",
    " * 当程序比较复杂时，一般将反复执行的模块封装为函数。\n",
    " * 一组相关的函数一般封装为一个模块，一个模块由一个头文件定义，由包含该头文件的C文件实现。\n",
    " * 封装的函数可被其他程序反复调用（现代工程一般较大，导入了大量不需要使用的库文件）。\n",
    " * C语言中，一般将多个函数共同操作的变量定义为全局的静态变量。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "* 例: 统计以下诗歌中包含字符串\"es\"的行数。  char t[]={'e','s','\\0'}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<div style=\" overflow: hidden;\n",
    "    background-color: silver;\">\n",
    "<div style=\"display: inline-block;\n",
    "   position: relative;\n",
    "   left: 50%;\n",
    "   background-color: silver;\">\n",
    "    <div style=\"display: inline-block;\n",
    "    position: relative;\n",
    "    left: -50%;\n",
    "    width:320px;\n",
    "    background-color: white;\">\n",
    "    <p style=\"text-align: left; font-size:15px; font-weight:normal;\">   \n",
    "    EVEN as the sun with purple-colour'd face<br>\n",
    "    Had ta'en his last leave of the weeping morn,<br>\n",
    "    Rose-cheek'd Adonis hied him to the chase;<br>\n",
    "    Hunting he loved, but love he laugh'd to scorn;<br>\n",
    "    Sick-thoughted Venus makes amain unto him,<br>\n",
    "    And like a bold-faced suitor 'gins to woo him.<br>\n",
    "    </p><p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    'Thrice-fairer than myself,' thus she began,<br>\n",
    "    'The field's chief flower, sweet above compare,<br>\n",
    "    Stain to all nymphs, more lovely than a man,<br>\n",
    "    More white and red than doves or roses are;<br>\n",
    "    Nature that made thee, with herself at strife,<br>\n",
    "    Saith that the world hath ending with thy life.<br>\n",
    "    </p><p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    'Vouchsafe, thou wonder, to alight thy steed,<br>\n",
    "    And rein his proud head to the saddle-bow;<br>\n",
    "    If thou wilt deign this favour, for thy meed<br>\n",
    "    A thousand honey secrets shalt thou know:<br>\n",
    "    Here come and sit, where never serpent hisses,<br>\n",
    "    And being set, I'll smother thee with kisses;<br>\n",
    "    </p><p style=\"text-align: left; font-size:15px; font-weight:normal;\">\n",
    "    'And yet not cloy thy lips with loathed satiety,<br>\n",
    "    But rather famish them amid their plenty,<br>\n",
    "    Making them red and pale with fresh variety,<br>\n",
    "    Ten kisses short as one, one long as twenty:<br>\n",
    "    A summer's day will seem an hour but short,<br>\n",
    "    Being wasted in such time-beguiling sport.'<br>\n",
    " </p><div></div></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "思路： 逐行查找字符串es，找到的话统计量+1。以剩余行为空作为中之条件。<br>\n",
    "C语言伪代码："
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```C\n",
    "int counter=0;\n",
    "while(line=读取一行)\n",
    "    if(line包含 \"es\") counter++; \n",
    "printf(\"%d\\n\",counter);\n",
    "//需要实现的功能： 读取一行\n",
    "//              判断一行字符串是否包含\"es\"\n",
    "//              需要一个记录字符串读取起始位值的操作。\n",
    "```\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "//读取一行，从起始位值p开始，结束后将p置于下一行起始处。\n",
    "int readline(char line[]){\n",
    "int i;  //auto variable, 内部变量\n",
    "if(str[p]=='\\0') return 0;\n",
    "while(str[p]=='\\n') p++;    \n",
    "for(i=p;str[i]!='\\n'&&str[i]!='\\0';i++) line[i-p]=str[i];\n",
    "line[i-p]='\\0';\n",
    "p=i;\n",
    "return 1;\n",
    "}     //p在哪里？ str在哪里？\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "//判断一个字符串是否包含另一个短字符串。泛化功能：判断查找字符串在行串中的起始位值。\n",
    "int strindex(char line[],char t[]){\n",
    "int i,j;\n",
    "    for(i=0;line[i]!='\\0';i++){\n",
    "       for(j=0;line[i+j]==t[j]&&t[j]!='\\0';); \n",
    "          if(t[j]=='\\0') return i;\n",
    "          j++;\n",
    "        }\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**合并**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6 lines include:es\n"
     ]
    }
   ],
   "source": [
    "#include <stdio.h>\n",
    "static char str[]=\"EVEN as the sun with purple-colour\\'d face\\nHad ta'en his last leave of the weeping morn,\\nRose-cheek'd Adonis hied him to the chase;\\nHunting he loved, but love he laugh'd to scorn;\\nSick-thoughted Venus makes amain unto him,\\nAnd like a bold-faced suitor 'gins to woo him'.\\n\\n'Thrice-fairer than myself,' thus she began,\\n'The field's chief flower, sweet above compare,\\nStain to all nymphs, more lovely than a man,\\nMore white and red than doves or roses are;\\nNature that made thee, with herself at strife,\\nSaith that the world hath ending with thy life.\\n\\n'Vouchsafe, thou wonder, to alight thy steed,\\nAnd rein his proud head to the saddle-bow;\\nIf thou wilt deign this favour, for thy meed\\nA thousand honey secrets shalt thou know:\\nHere come and sit, where never serpent hisses,\\nAnd being set, I'll smother thee with kisses;\\n\\n'And yet not cloy thy lips with loathed satiety,\\nBut rather famish them amid their plenty,\\nMaking them red and pale with fresh variety,\\nTen kisses short as one, one long as twenty:\\nA summer's day will seem an hour but short,\\nBeing wasted in such time-beguiling sport.\";\n",
    "static int p=0;    \n",
    "int readline(char line[]){\n",
    "int i;  //auto variable, 内部变量\n",
    "if(str[p]=='\\0') return 0;\n",
    "while(str[p]=='\\n') p++;    \n",
    "for(i=p;str[i]!='\\n'&&str[i]!='\\0';i++) line[i-p]=str[i];\n",
    "line[i-p]='\\0';\n",
    "p=i;\n",
    "return 1;\n",
    "}    \n",
    "//判断一个字符串是否包含另一个短字符串。泛化功能：判断查找字符串在行串中的起始位值。\n",
    "int strindex(char line[],char t[]){\n",
    "int i,j;\n",
    "    for(i=0;line[i]!='\\0';i++){\n",
    "       for(j=0;line[i+j]==t[j]&&t[j]!='\\0';j++);\n",
    "          if(t[j]=='\\0') return i;\n",
    "        }\n",
    "    return -1;\n",
    "}\n",
    "int main(){\n",
    "int counter=0;\n",
    "char line[1000];\n",
    "char t[]=\"es\";    \n",
    "while(readline(line)) if(strindex(line,t)>=0) counter++; \n",
    "printf(\"%d lines include:%s\\n\",counter,t);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-66  -21  -15  -3  12  20  23  23  33  34  34  45  56  76  77  79  89  \n"
     ]
    }
   ],
   "source": [
    "//将以下排序算法（堆排序）进行函数封装，\n",
    "//使主函数main()中不显式包含排序逻辑。 \n",
    "#include <stdio.h>\n",
    "void swap(int* a, int*b){\n",
    "int tmp = *a;\n",
    "*a      = *b;\n",
    "*b      = tmp;\n",
    "}\n",
    "void adjust_heap(int* arr, int top,int N){\n",
    "int tmp = arr[top];\n",
    "for(int j=top*2+1;j<N;j=j*2+1){\n",
    "if(arr[j]<arr[j+1]&&(j+1)<N) j++;\n",
    "if(tmp<arr[j]){ \n",
    "arr[top]=arr[j];\n",
    "top = j;\n",
    "}else break;\n",
    "}\n",
    "arr[top] = tmp;\n",
    "\n",
    "}\n",
    "void create_heap(int* arr, int N){\n",
    "for(int i=N/2-1;i>=0;i--) adjust_heap(arr,i,N);\n",
    "}\n",
    "void print_n(int* arr, int n){\n",
    "for(int i=0;i<n;i++) printf(\"%d  \",arr[i]);\n",
    "printf(\"\\n\");\n",
    "}\n",
    "void heapsort(int arr[],int length){\n",
    "create_heap(arr,length);\n",
    "//printf(\"%d\",arr[0]);\n",
    "for(int n=length;n>1;n--)\n",
    "{\n",
    "swap(&arr[0],&arr[n-1]);\n",
    "adjust_heap(arr,0,n-1);\n",
    "}\n",
    "}\n",
    "int main(){\n",
    "int arr[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "heapsort(arr,17);\n",
    "print_n(arr,17);\n",
    "return 0;  // cong create_heap 到下面一整个for-loop. 我希望将它封装为一个函数—— (返回值)heap_sort(参数？)。\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**更进一步**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "// m_strop.h\n",
    "static char str[]=\"EVEN as the sun with purple-colour\\'d face\\nHad ta'en his last leave of the weeping morn,\\nRose-cheek'd Adonis hied him to the chase;\\nHunting he loved, but love he laugh'd to scorn;\\nSick-thoughted Venus makes amain unto him,\\nAnd like a bold-faced suitor 'gins to woo him'.\\n\\n'Thrice-fairer than myself,' thus she began,\\n'The field's chief flower, sweet above compare,\\nStain to all nymphs, more lovely than a man,\\nMore white and red than doves or roses are;\\nNature that made thee, with herself at strife,\\nSaith that the world hath ending with thy life.\\n\\n'Vouchsafe, thou wonder, to alight thy steed,\\nAnd rein his proud head to the saddle-bow;\\nIf thou wilt deign this favour, for thy meed\\nA thousand honey secrets shalt thou know:\\nHere come and sit, where never serpent hisses,\\nAnd being set, I'll smother thee with kisses;\\n\\n'And yet not cloy thy lips with loathed satiety,\\nBut rather famish them amid their plenty,\\nMaking them red and pale with fresh variety,\\nTen kisses short as one, one long as twenty:\\nA summer's day will seem an hour but short,\\nBeing wasted in such time-beguiling sport.\";\n",
    "static int p=0;    \n",
    "int readline(char line[]){\n",
    "int i;  //auto variable, 内部变量\n",
    "if(str[p]=='\\0') return 0;\n",
    "while(str[p]=='\\n') p++;    \n",
    "for(i=p;str[i]!='\\n'&&str[i]!='\\0';i++) line[i-p]=str[i];\n",
    "line[i-p]='\\0';\n",
    "p=i;\n",
    "return 1;\n",
    "}    \n",
    "//判断一个字符串是否包含另一个短字符串。泛化功能：判断查找字符串在行串中的起始位值。\n",
    "int strindex(char line[],char t[]){\n",
    "int i,j;\n",
    "    for(i=0;line[i]!='\\0';i++){\n",
    "       for(j=0;line[i+j]==t[j]&&t[j]!='\\0';j++);\n",
    "          if(t[j]=='\\0') return i;\n",
    "        }\n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* 递归函数： int funca(int n){ codeblock;funca(n-1);codeblock;}\n",
    "* 函数自身调用自身。\n",
    "* 一般在程序设计过程中，将一个大问题（如数组排序）分解为若干个小问题，发现部分小问题与大问题的定义方式基本一样。 n！=n*(n-1)! \n",
    "\n",
    "* 此时适合采用递归进行程序的设计与实现。\n",
    "* 线性递归： \n",
    " * A(n)$\\rightarrow$A(n-1)$\\rightarrow$A(n-2)$\\rightarrow \\cdots$A(1)$\\downarrow$\n",
    " * A(n)$\\leftarrow \\cdots$A(3)$\\leftarrow$A(2)$\\leftarrow$A(1) \n",
    "* 递归的优点： 代码紧凑，结构清析。\n",
    "* 递归的缺点： 执行速度慢,内存开销大。\n",
    "* 要点：\n",
    " 1. 确定终止条件！\n",
    " 2. 确定结构关系！"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2432902008176640000"
     ]
    }
   ],
   "source": [
    "// 阶乘递归算法\n",
    "/*\n",
    "long factorial(int n){\n",
    "if(n==1) return 1;\n",
    "return n*factorial(n-1);\n",
    "}\n",
    "*/\n",
    "#include <stdio.h>\n",
    "long factorial(int n){\n",
    "    return n==1?1:n*factorial(n-1); \n",
    "}\n",
    "int main(){\n",
    "    printf(\"%ld\",factorial(20));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "the gcd of (162,72) is 18"
     ]
    }
   ],
   "source": [
    "// 求最大公约数\n",
    "// 辗转相除法（欧几里德算法）\n",
    "#include <stdio.h>\n",
    "int gcd(int a, int b){ // greatest common divisor\n",
    "    if(a%b==0) return b;\n",
    "    else return gcd(b,a%b);\n",
    "}                      \n",
    "int main(){\n",
    "    printf(\"the gcd of (%d,%d) is %d\", 162,72,gcd(162,72));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "put disk from A to C\n",
      "put disk from A to B\n",
      "put disk from C to B\n",
      "put disk from A to C\n",
      "put disk from B to A\n",
      "put disk from B to C\n",
      "put disk from A to C\n"
     ]
    }
   ],
   "source": [
    "//非线性递归。\n",
    "//函数的递归调用，汉诺塔！  非线性递归，或者说树形递归。\n",
    "#include <stdio.h>\n",
    "void hanoi(int disks,char from,char to,char temp){\n",
    "if(disks==1) {\n",
    "printf(\"put disk from %c to %c\\n\", from,to);\n",
    "return;\n",
    "}\n",
    "hanoi(disks-1,from,temp,to);  //将98个圆盘从A移动到B \n",
    "printf(\"put disk from %c to %c\\n\", from,to);//老和尚将最底下的圆盘从A移动到C\n",
    "hanoi(disks-1,temp,to,from);  //将98个圆盘从B移动到C  \n",
    "}\n",
    "int main(){\n",
    "    hanoi(99,'A','C','B');\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "put disk from A to C\n",
      "put disk from A to B\n",
      "put disk from C to B\n",
      "put disk from A to C\n",
      "put disk from B to A\n",
      "put disk from B to C\n",
      "put disk from A to C\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[C kernel] Executable exited with code 255"
     ]
    }
   ],
   "source": [
    "//任意递归函数均可使用堆栈与循环实现（难度较大）。\n",
    "//汉诺塔的非递归实现！（等效于完全二叉树的中序遍历）\n",
    "#include <stdio.h>\n",
    "#define  maxelement 5000;\n",
    "typedef struct {int disks;char from;char to;char temp;} argshanoi;\n",
    "static argshanoi elements[5000];\n",
    "static int t = -1;\n",
    "static int isStackEmpty(){\n",
    "    if(t==-1) return 1;\n",
    "        else return 0;\n",
    "}\n",
    "static void push(argshanoi element){\n",
    "    elements[++t]=element;\n",
    "}\n",
    "static argshanoi argshanoi pop(){\n",
    "    return elements[t--];\n",
    "}\n",
    "\n",
    "int main(){\n",
    "  argshanoi root;root.disks=3,root.from='A',root.to='C',root.temp='B';\n",
    "  argshanoi right;argshanoi pre;argshanoi current;\n",
    "  push(root);\n",
    "  do{\n",
    "  pre=pop();    \n",
    "  current.disks=pre.disks-1,current.from=pre.from, current.to=pre.temp,current.temp=pre.to;\n",
    "  push(pre);\n",
    "  push(current);    \n",
    "  }while(current.disks!=1);\n",
    "  while(!isStackEmpty()){\n",
    "  current=pop();\n",
    "  printf(\"put disk from %c to %c\\n\",current.from,current.to);    \n",
    "  if(current.disks==1) continue;\n",
    "  right.disks=current.disks-1,right.from=current.temp,right.to=current.to,right.temp=current.from;\n",
    "  push(right);\n",
    "  do{\n",
    "  pre=pop();    \n",
    "  if(pre.disks==1){push(pre);break;}\n",
    "  current.disks=pre.disks-1,current.from=pre.from, current.to=pre.temp,current.temp=pre.to;\n",
    "  push(pre);\n",
    "  push(current);        \n",
    "  }while(current.disks!=1);\n",
    "  }  \n",
    "  return -1; \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "//快速排序\n",
    "void swap(int* a, int*b){\n",
    "int tmp = *a;\n",
    "*a      = *b;\n",
    "*b      = tmp;\n",
    "}\n",
    "#include <stdio.h>\n",
    "void print_n(int* arr, int n){\n",
    "for(int i=0;i<n;i++) printf(\"%d  \",arr[i]);\n",
    "printf(\"\\n\");\n",
    "}\n",
    "int put_last(int*arr, int left ,int right){\n",
    "int i=left,j=right,tmp=arr[i];\n",
    "while(i<j){\n",
    "while(i<j&&arr[j]>=tmp){j--;}; arr[i]=arr[j];\n",
    "while(i<j&&arr[i]<=tmp){i++;}; arr[j]=arr[i];\n",
    "}\n",
    "arr[i]=tmp;\n",
    "return i;\n",
    "}\n",
    "void quick_sort(int* arr, int left,int right){\n",
    "if(left<right){\n",
    "int b = put_last(arr,left,right); // arr中第一个元素的位置k，arr[]    arr[0~k-1] arr[k+1,n]\n",
    "quick_sort(arr,left,b-1);\n",
    "quick_sort(arr,b+1,right);   //非递归实现，\n",
    "}\n",
    "}\n",
    "\n",
    "int main(){\n",
    "int arr[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "quick_sort(arr,0,16);\n",
    "print_n(arr,17);\n",
    "return 0;\n",
    "}\n",
    "//尝试将快排使用非递归实现。 "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 函数变量的作用域\n",
    "* **自动变量**  几乎可定义于任何位置 \n",
    "* **静态变量**  同上，可见范围同上。生命周期不同"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "```C\n",
    "static int T1; // 定义在函数域外的静态变量\n",
    "int outer;  // 定义在函数域外的自动变量 int funcb { }    func(a,b)\n",
    "   int func(int a,int c){    //参数a，b视作内部变量, 函数内部所有域均可见。\n",
    "    \n",
    "    int inner;          //定义内部变量\n",
    "    static int T2;\n",
    "       {\n",
    "        ...\n",
    "        int innerfield;    //innerfield在{...} 外部不可见,但该域可见inner，outer。\n",
    "        static int T3;\n",
    "        inner ,T2,a, c , outer, T1.    \n",
    "           \n",
    "        ...                    \n",
    "        {\n",
    "           int innerinnerfield; //域中可有域，该域可见inner，innerfield，outer。\n",
    "           static int T4; \n",
    "            \n",
    "            \n",
    "        }\n",
    "        \n",
    "       \n",
    "       }\n",
    "    innerfield, T3. //  undefined.    \n",
    "       \n",
    "       \n",
    "       \n",
    "}// 外部静态变量T1,外部变量outer均按序全局可见。\n",
    " // 静态变量的可见规则与自动变量相同，但是一经定义，在内存中一直存在，直到程序退出。\n",
    " \n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0\n",
      "1\n",
      "18\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[C kernel] Executable exited with code 255"
     ]
    }
   ],
   "source": [
    "#include<stdio.h> \n",
    "static int T1=0;  // 定义在函数域外的静态变量\n",
    "int outer=1;      // 定义在函数域外的自动变量\n",
    "   int* func(int a,int b){  //参数a，b视作函数域内变量, 函数内部所有域均可见，被调用时赋值。\n",
    "    \n",
    "    int inner=4;          //函数域内的自动变量\n",
    "    static int T2=5;      //函数域内静态变量\n",
    "    {\n",
    "       \n",
    "        int innerfield=6;    //innerfield在{...} 外部不可见,但该域可见inner，outer。\n",
    "        static int T3=7;\n",
    "        //return &T3;//return &innerfield;                   \n",
    "        {\n",
    "           int innerinnerfield=8; //域中可有域，该域可见inner，innerfield，outer。\n",
    "           static int T4;\n",
    "           T4=a+b+outer+T3+T2+T1; \n",
    "           return &T4; //直接退出函数栈，返回变量T4的地址。\n",
    "           \n",
    "        }\n",
    "        \n",
    "        printf(\"T3=%d\\n\",T3);\n",
    "        printf(\"T2=%d\\n\",T2);\n",
    "        printf(\"innerfield=%d\\n\",innerfield);\n",
    "        printf(\"a=%d\\n\",a);\n",
    "        printf(\"b=%d\\n\",b);\n",
    "    }\n",
    "    printf(\"T2=%d\\n\",T2);\n",
    "  \n",
    "}\n",
    "int main(){\n",
    "    int* test=func(2,3);\n",
    "    printf(\"%d\\n\",T1);\n",
    "    printf(\"%d\\n\",outer);\n",
    "    printf(\"%d\\n\",*test);\n",
    "    return -1;\n",
    "}\n",
    "//总结，内层域总可见外层域中的变量，外层域不可见内层域中的变量；静态变量一经定义一直存在于内存中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 外部变量，\n",
    "* 当变量定义于某个文件时，我们需要在使用该变量的文件中声明同名的外部变量。\n",
    "* 变量被static修饰为静态变量时，不可被外部引用。\n",
    "* extern 修饰符的作用主要为添加操作头文件中定义为函数外部自动变量的函数。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```C\n",
    "//testextern.h\n",
    "   static int T1=0;  // static静态变量不能补声明为外部变量\n",
    "   int outer=1;      // 定义在函数域外的自动变量\n",
    "   int* func(int a,int b){  //参数a，b视作函数域内变量, 函数内部所有域均可见，被调用时赋值。\n",
    "    \n",
    "    int inner=4;          //函数域内的自动变量\n",
    "    static int T2=5;\n",
    "    {\n",
    "       \n",
    "        int innerfield=6;    //innerfield在{...} 外部不可见,但该域可见inner，outer。\n",
    "        static int T3=7;\n",
    "        //return &T3;//return &innerfield;                   \n",
    "        {\n",
    "           int innerinnerfield=8; //域中可有域，该域可见inner，innerfield，outer。\n",
    "           static int T4;\n",
    "           T4=a+b+outer+T3+T2+T1; \n",
    "           return &T4; //直接退出函数栈，返回变量T4的地址。\n",
    "        }\n",
    "        printf(\"%d\\n\",T3);\n",
    "        printf(\"%d\\n\",T2);\n",
    "        printf(\"%d\\n\",innerfield);\n",
    "        printf(\"%d\\n\",a);\n",
    "        printf(\"%d\\n\",b);\n",
    "    }\n",
    "    printf(\"%d\\n\",T2);\n",
    "}\n",
    "//\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "```C\n",
    "//testextern.c\n",
    "#include \"testextern.h\"\n",
    "#include <stdio.h>\n",
    "extern int outer;  //\n",
    "int main(){\n",
    "    printf(\"%d\",outer);\n",
    "    return -1;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 函数指针\n",
    "*  一般定义方式：    int(或其它返回类型) (* pfunc)(int a,int b,char c\\[\\]...);\n",
    "*  数组形式：        int(或其它返回类型) (* pfuncs\\[4\\])(int a,int b,char c\\[\\]...)={max,min,sort,...};\n",
    "*  指针赋值:         pfuncs = funcname(函数名);   (函数名亦为内存地址的别名)\n",
    "*  函数的指针调用1：  pfunc(a,b,c,...)；   pfunc 指向max(a,b,c...),  pfunc(a,b,c). max(a,b,c...) \n",
    "*  数组赋值：        pfuncs\\[i\\]=funcname(函数名);  \n",
    "*  函数的指针调用2：  pfuncs\\[i\\](a,b,c...);\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Applying quicksort!\n",
      "-66  -21  -15  -3  12  20  23  23  33  34  34  45  56  76  77  79  89  \n",
      "Applying heapsort!\n",
      "-66  -21  -15  -3  12  20  23  23  33  34  34  45  56  76  77  79  89  \n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[C kernel] Executable exited with code 255"
     ]
    }
   ],
   "source": [
    "#include <stdio.h>\n",
    "void print_n(int* arr, int n);\n",
    "void swap(int* a, int*b){  //一个内存地址的别名。    可以赋值给一个指向函数的指针变量（函数指针）。//指针数组 int* a[]，数组指针 int (* a)[3]  a+1.      \n",
    "int tmp = *a;\n",
    "*a      = *b;\n",
    "*b      = tmp;\n",
    "}\n",
    "int put_first(int*arr, int left ,int right){\n",
    "int i=left,j=right,tmp=arr[i];\n",
    "while(i<j){\n",
    "while(i<j&&arr[j]>=tmp){j--;}; arr[i]=arr[j];\n",
    "while(i<j&&arr[i]<=tmp){i++;}; arr[j]=arr[i];\n",
    "}\n",
    "arr[i]=tmp;\n",
    "return i;\n",
    "}\n",
    "void quick_sort(int* arr, int left,int right){\n",
    "if(right==16&&left==0) printf(\"Applying quicksort!\\n\");\n",
    "if(left<right){\n",
    "int b = put_first(arr,left,right); // arr中第一个元素的位置k，arr[]    arr[0~k-1] arr[k+1,n]\n",
    "quick_sort(arr,left,b-1);\n",
    "quick_sort(arr,b+1,right);   //非递归实现，\n",
    "}\n",
    "}\n",
    "\n",
    "void print_n(int* arr, int n){\n",
    "for(int i=0;i<n;i++) printf(\"%d  \",arr[i]);\n",
    "printf(\"\\n\");\n",
    "}\n",
    "\n",
    "void adjust_heap(int* arr, int top,int N){\n",
    "int tmp = arr[top];\n",
    "for(int j=top*2+1;j<N;j=j*2+1){\n",
    "if(arr[j]<arr[j+1]&&(j+1)<N) j++;\n",
    "if(tmp<arr[j]){ \n",
    "arr[top]=arr[j];\n",
    "top = j;\n",
    "}else break;\n",
    "}\n",
    "arr[top] = tmp;\n",
    "\n",
    "}\n",
    "void create_heap(int* arr, int N){\n",
    "for(int i=N/2-1;i>=0;i--) adjust_heap(arr,i,N);\n",
    "}\n",
    "void heap_sort(int* arr,int left,int right){\n",
    "printf(\"Applying heapsort!\\n\");\n",
    "int length=right+1;\n",
    "create_heap(arr,length);\n",
    "for(int n=length;n>1;n--)\n",
    "{\n",
    "swap(&arr[0],&arr[n-1]);\n",
    "adjust_heap(arr,0,n-1);\n",
    "}\n",
    "}\n",
    "int main(){\n",
    "    int arr1[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "    int arr2[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "    /*\n",
    "    void (* funcp)(int* arr,int left,int right);\n",
    "    funcp=quick_sort;\n",
    "    (funcp)(arr1,0,16);\n",
    "    print_n(arr1,17);\n",
    "    funcp=heap_sort;\n",
    "    (funcp)(arr2,0,16);\n",
    "    print_n(arr2,17);\n",
    "    */\n",
    "    /*\n",
    "    void (* funcps[2])(int* arr,int left,int right);\n",
    "    funcps[0]=quick_sort;\n",
    "    funcps[1]=heap_sort;\n",
    "    int* aptr[2];aptr[0]=arr1,aptr[1]=arr2;\n",
    "    for(int i=0;i<2;i++){\n",
    "         (funcps[i])(aptr[i],0,16);\n",
    "         print_n(aptr[i],17);\n",
    "    }*/\n",
    "    \n",
    "    void (*funcps[2])(int* arr,int left,int right)={quick_sort,heap_sort};\n",
    "    int* aptr[2];aptr[0]=arr1,aptr[1]=arr2;\n",
    "    for(int i=0;i<2;i++){\n",
    "         funcps[i](aptr[i],0,16);\n",
    "         print_n(aptr[i],17);\n",
    "    }\n",
    "       \n",
    "    return -1;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**作业1： 将以下排序方法放在上述文件中，以函数指针数组的形式进行调用。**<br>\n",
    "**作业2： 将所有排序方法打包为头文件，并在主文件中以指针数组的形式调用成功**<br>\n",
    "**注意！并归排序可不做，尝试看懂并改进**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "//选择排序\n",
    "void selectn(int* arr,int n){\n",
    "for(int i=0;i<n;i++)\n",
    "if(arr[i]>arr[n]){\n",
    "int temp = arr[i];\n",
    "arr[i]   = arr[n];\n",
    "arr[n]     = temp;\n",
    "} \n",
    "}\n",
    "int main(){\n",
    "int arr[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "for(int n=16;n>=0;n--)\n",
    "{\n",
    "selectn(arr,n);\n",
    "print_n(arr,17);\n",
    "}\n",
    "return 0;\n",
    "}\n",
    "//插入排序\n",
    "void insertn(int* arr,int n,int N){       45,23,12,-15,76,34,77,23,-66,34,-3,20,33,56,79,-21,89\n",
    "for(int j=n;j<(N-1);j++)\n",
    "if(arr[j]>arr[j+1])\n",
    "swap(&arr[j],&arr[j+1]);\n",
    "}\n",
    "\n",
    "void insertsort(int* arr, int N){\n",
    "    for(int n=16;n>=0;n--)\n",
    "        insertn(arr,n,17);\n",
    "}\n",
    "\n",
    "\n",
    "int main(){\n",
    "int arr[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "insertsort(arr,17);\n",
    "return 0;\n",
    "}\n",
    "//冒泡排序 //O(n^2)\n",
    "void bubble(int* arr,int n){\n",
    "for(int i=0;i<n;i++)\n",
    "if(arr[i]>arr[i+1]) swap(&arr[i],&arr[i+1]);\n",
    "}\n",
    "int main(){\n",
    "int arr[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "for(int n=16;n>=0;n--)\n",
    "{\n",
    "bubble(arr,n);\n",
    "print_n(arr,17);\n",
    "}\n",
    "return 0;\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23  45  -15  12  34  76  23  77  -66  34  20  89  33  56  -21  79  -3  \n",
      "-15  12  23  45  23  34  76  77  -66  20  34  89  -21  33  56  79  -3  \n",
      "-15  12  23  23  34  45  76  77  -66  -21  20  33  34  56  79  89  -3  \n",
      "-66  -21  -15  12  20  23  23  33  34  34  45  56  76  77  79  89  -3  \n",
      "-66  -21  -15  -3  12  20  23  23  33  34  34  45  56  76  77  79  89  \n"
     ]
    }
   ],
   "source": [
    "//并归排序  O(nlog(n))\n",
    "#include <stdio.h>\n",
    "#include <malloc.h>\n",
    "#define MIN(a,b) a<b?a:b //宏定义条件判断表达式\n",
    "void print_n(int* arr, int n){\n",
    "for(int i=0;i<n;i++) printf(\"%d  \",arr[i]);\n",
    "printf(\"\\n\");\n",
    "}\n",
    "\n",
    "void merge(int* arr1, int* arr2, int s, int m, int t){ \n",
    "//将有序数组A=arr1[s~m-1],B=arr1[m~t-1]合并为有序数组arr2[s~t-1]\n",
    "if(m!=t){\n",
    "int pl=s; //pl指向数组A=arr1[s~m-1]中首个 **未移动到数组C=arr2[s~t-1]中的元素** 的序数\n",
    "int pr=m; //pr指向数组B=arr1[m~t-1]中首个 **未移动到数组C=arr2[s~t-1]中的元素** 的序数\n",
    "for(int i=s;i<t;i++) {// 处理合并两个数组的情况;A,B不一定等长\n",
    "if((m-pl)==0&&(t-pr)>0) {arr2[i]=arr1[pr++];continue;} \n",
    "// 判断数组A=arr1[s~m-1]中的元素是否已经完全移出,如果是将B=arr1[m~t-1]中的剩余数全部移出到到数组C\n",
    "if((t-pr)==0&&(m-pl)>0) {arr2[i]=arr1[pl++];continue;} \n",
    "// 判断数组B=arr1[m~t-1]中的元素是否已经完全移出,如果是将A=arr1[s~m-1]中的剩余数全部移出到到数组C\n",
    "arr2[i]=(arr1[pl]<arr1[pr])?arr1[pl++]:arr1[pr++];\n",
    "}\n",
    "}else{\n",
    "for(int i=s;i<t;i++) arr2[i]=arr1[i]; //处理尾端只剩一个数组的情况,直接按序赋值\n",
    "}\n",
    "}\n",
    "\n",
    "void Merge_Sort(int** arr1, int** arr2,int N){\n",
    "for(int len=1;len<N;len*=2)\n",
    "{\n",
    "for(int i=0;i<N;i+=(2*len)) merge(*arr1,*arr2,i,MIN(i+len,N),MIN(i+2*len,N)); \n",
    "// 分段合并有序序列并考虑以下两种情况\n",
    "// 1. i+len<N; 2. 1+2len<N\n",
    "// 第一种情况： 分段后，数组尾端只剩一个数组\n",
    "// 第二种情况： 分段后，数组尾端有两个数组，但不等长。\n",
    "int* tmp    =  *arr1;\n",
    "*arr1       =  *arr2;\n",
    "*arr2       =   tmp;\n",
    "print_n(*arr1,17);\n",
    "}\n",
    "}\n",
    "void main(){\n",
    "int arr[17]={45,23,12,-15,76,34,77,23,-66,34,89,20,33,56,79,-21,-3};\n",
    "int arr1[17];\n",
    "int* parr1 = arr;\n",
    "int* parr2 = arr1;\n",
    "Merge_Sort(&parr1,&parr2,17);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C",
   "language": "c",
   "name": "c"
  },
  "language_info": {
   "file_extension": ".c",
   "mimetype": "text/plain",
   "name": "c"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
